package java学习.算法.排序;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/7/6 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */

import java学习.实训.day08.Int;

import java.util.*;

/**
 * 如何得到一个数据流中的中位数？
 * 如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
 * 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
 * 我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
 */
public class 数据流中的中位数 {
    public static void main(String[] args) {

    }
    private final List<Integer> list = new ArrayList<Integer>();

    public void Insert1(Integer num) {
        list.add(num);
    }
//  0 1 2 3 4 5 6 7
//  1 1 1 1 1 1 1 1
    public Double GetMedian1() {
        int size = list.size();
        double result = 0;
//        1. 判断size是否为0，为0则 不需要排序。
        if (size!=0){

            Collections.sort(list);
            if (size%2==0){
                Integer it1 =  list.get(size / 2);
                Integer it2 =  list.get((size / 2)-1);
                result =  (it1+it2)/2.0;
            }else{ // 奇数
                result =  list.get(size/2);
            }

        }
        return result;
    }

    Queue<Integer>  minQ = new PriorityQueue<>();

    Queue<Integer>  maxQ = new PriorityQueue<>(new Comparator<Integer>(){
        @Override
        public int compare(Integer o1, Integer o2){
            return o2-o1;
        }
    });

    int count = 0;

    /**
     *  插入元素： 当count是奇数： 放入大根堆， 偶数放入小根堆
     *  若maxQ的根 > minQ的根， 交换
     *  反之亦交换
     * @param num
     */
    public void Insert(Integer num) {
        if (count%2==0){
            if (maxQ.peek() > num && !maxQ.isEmpty()){ // 尽量将小的放入 maxQ
                maxQ.offer(num);
                num = maxQ.poll();  // 将maxQ的 堆顶给 minQ
            }
            minQ.offer(num);        // 置换出大的数给 minQ
        }else{
            if (minQ.peek() < num && !minQ.isEmpty()){
                minQ.offer(num);
                 num = minQ.poll(); // 将maxQ的 堆顶给 minQ
            }
            maxQ.offer(num);
        }
        count++;

    }

    public Double GetMedian() {
        double result = 0;
        if (maxQ.size() == minQ.size()){
          // 是偶数，求平均值
            result = (maxQ.peek()+ minQ.peek())/2.0;
        }else if (maxQ.size() > minQ.size()){
            result = maxQ.peek()*1.0;
        }else {
            result = minQ.peek()*1.0;
        }
        return  result;
    }

}
